//! 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
//!不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//!元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
//! 

use std::num;

struct  Solution;

impl Solution {

    /// 这个算法是采用单指针right，每一项和目标值做比较，如果不相等，就把当前值给right下标的位置，right再递增。
    /// 问题是这个算法每一项都要做移动，其实我们应该在相等的时候在移动，这要看第二个算法
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        if nums.len()<1 {
            return 0;
        }
        let mut right:usize = 0;
        for i in 0..nums.len() {
            if nums[i] != val {
                nums[right] = nums[i];
                right += 1;
            } 
        }
        right as i32
    }

    /// 这个算法的思路是通过双指针,从left=0开始，如果等于目标值，则和最后一个做交换 right递增，直到=left位置，
    /// 最后返回left的值
    pub fn remove_element2(nums: &mut Vec<i32>, val: i32) -> i32 {
        if nums.len()<1 {
            return 0;
        }
        let mut left = 0_usize;
        let mut right:usize = nums.len()-1;
        while left < right {
            if nums[left] == val {
                for i in ((left+1) ..=right).rev()  {
                    println!("oo:{}", i);
                    if nums[i] != val {
                        let tmp = nums[left];
                        nums[left] = nums[i];
                        nums[i] = tmp;
                        right -= 1;
                        left += 1;
                        println!("kk left{},right:{}", left,right);
                        break;
                    } else {
                        right -= 1;
                    }
                    println!("tt left{},right:{}", left,right);
                }
            } else {
                println!("ss left{},right:{}", left,right);
                left += 1;
            }
        }
        println!("最终：{}", left);
        let mut count = left as i32;
        if nums[left] == val {
            count -= 1;
        } 
        count+1
    }


}

#[cfg(test)]
mod test {

    use super::*;

    #[test]
    fn remove_element1() {
        let mut nums1 = vec![4, 5, 6,4, 5, 1];
        let count = Solution::remove_element(&mut nums1, 5);
        println!("{:?}, 个数:{}", nums1, count);
    }

    #[test]
    fn remove_element12() {
        let mut nums1 = vec![1];
        let count = Solution::remove_element2(&mut nums1, 1);
        println!("{:?}, 个数:{}", nums1, count);

        let mut nums1 = vec![4, 5, 6,4, 5, 1];
        let count = Solution::remove_element2(&mut nums1, 5);
        println!("{:?}, 个数:{}", nums1, count);

        let mut nums1 = vec![4, 5];
        let count = Solution::remove_element2(&mut nums1, 4);
        println!("{:?}, 个数:{}", nums1, count);
    }

}